When rendering a page for printing and/or display, an intermediate description of the page is often given in a page description language, such as PostScript™ and PCL; or equivalently, as a set of descriptions of graphics objects provided in function calls to a graphics interface, such as the Windows GDI or X-11. The rules for rasterizing an object, whose description has been provided in terms of an edge on the page, are an inherent feature of the interface or page description language and vary according to the type of interface or page description language being used. The page is typically rendered for printing and/or display via said graphics interface by an object based graphics system.
Most of these object based graphics systems utilize a frame store or page buffer to hold a pixel-based image of the page or screen for subsequent printing and/or display. Typically, the outlines of the graphic objects are calculated, filled and written into the frame store. For two-dimensional graphics, objects which appear in front of other objects are simply written into the frame store after the background objects, thereby replacing the background on a pixel-by-pixel basis. This is commonly known in the art as the “Painter's algorithm”. Objects are considered in priority order, from the rearmost object to the foremost object, and, typically, each object is rasterized in scan line order and pixels are written to the frame store in sequential runs along each scan line.
There are essentially two problems with this technique. The first is that it requires fast random access to all the pixels in the frame store. This is because each new object considered could affect any pixel in the frame-store. For this reason, the frame store is normally kept in semiconductor random access memory (RAM). For high resolution color printers the amount of RAM required is very large, typically in excess of 100 MBytes, which is costly and difficult to operate at high speed. The second problem is that many pixels, which are painted (rendered), are over-painted (re-rendered) by later objects. Painting the pixels with the earlier objects was a waste of time.
One method for overcoming the large frame-store problem is the use of “banding”. When banding is used, only part of the frame-store exists in memory at any one time. All of the objects to be drawn are retained in a “display list”. The whole image is rendered as above, but pixel painting (rendering) operations that try to paint (render) outside the fraction of the frame-store which exists are “clipped” out. After all the objects have been drawn, the fractional part of the frame-store is sent to the printer (or some other location) and another fraction of the frame-store is selected and the process repeated. There are penalties with this technique. For example, the objects being drawn must be considered and re-considered many times—once for each band. As the number of bands increases, so too does the repetitious examination of objects requiring rendering. The technique of banding does not solve the problem of the cost of over-painting.
Some other graphic systems consider the image in scan line order. Again, all the objects to be drawn are retained in a display list. On each scan line the objects which intersect that scan line are then considered in priority order and for each object, spans of pixels between object edge intersection points are set in a line store. This technique also overcomes the large frame store problem, but still suffers from the over-paint problem.
Other graphic systems utilize pixel sequential rendering which overcomes both the large frame store problem and over-paint problem. In these systems, each scan line is produced in turn. Again, all the objects to be drawn are retained in a display list. On each scan line, the edges of objects which intersect that scan line are held in increasing order of their intersection with the scan line. These points of intersection, or edge crossings, are considered in turn and used to toggle an array of active fields. There is one active field for each object priority that is of interest on the scan line. Between each pair of edges considered, the color data for each pixel which lies between the first edge and the next edge is generated by using a priority encoder on the active flags to determine which priority is topmost, and using the color associated with that priority for the pixels of the span between the two edges. In preparation for the next scan line, the coordinate of intersection of each edge is updated in accordance with the nature of each edge. Adjacent edges, which become mis-sorted as a result of this update are swapped. New edges are also merged into the list of edges.
These graphic systems which use pixel sequential rendering have significant advantages in that there is no frame store or line store, there is no over painting, and the object priorities are dealt with in constant order time, rather than order N time (where N is the number of priorities). In these pixel sequential rendering graphic systems, the edges of objects are tracked independently of each other. These systems will render a reliable representation of the page provided that the rasterization rule, inherent in the graphics interface or page description language, for rounding the edge positions is the same for activation and deactivation of an object.
Turning now to FIG. 2A, there is illustrated one scanline 200a of an image comprising a plurality of pixels (represented as boxes) and two edges 202a, 203a of an exemplary object for explaining a typical prior art rasterization rule of a page description language. In this rasterization rule, the location of the edge crossing points (e.g., 204a, 205a) of the edges (e.g., 202a, 203a) are always mathematically rounded up to the location of the top left hand corner of the next pixel for both the activation and de-activation of an object. In this particular example, the active pixels of the object, that is all those pixels filled by the object are shown as boxes with cross-hatched filling. A typical pixel sequential rendering graphic system is able to implement such a rasterization rule as it can be applied to each edge independently irrespective of whether the object is to be activated or de-activated. However, there are page description languages and interfaces where the rasterization rule for rounding of edge position is dependent on whether an object is being activated or deactivated. A particular case in point is the prior art rasterization rule of the page description language PostScript™, that specifies that all pixels, which are touched by the edges of an object, are filled by that object.
Turning now to FIG. 1, there is illustrated a plurality of scanlines 100a of an image each comprising a plurality of pixels (represented as boxes) and a number of edges 102a, 104a, 106a, 108a of an exemplary object for explaining such a rasterization rule. Again, the active pixels of the object, that is all those pixels filled by the object are shown as boxes with cross-hatched filling. As can be seen all those pixels touched by the edges 102a, 104a, 106a, 108a of the exemplary object are active. Thus, the position of the edge must be rounded down for activation, and rounded up for de-activation. Turning now to FIG. 2B, there is illustrated one scanline 210b of an image comprising a plurality of pixels (represented as boxes) and two edges 212b, 213b of an exemplary object for explaining the prior art rasterization rule of the page description language PostScript™ in more detail. The two edges 212b, 213b of the exemplary object intersect the scanline 210b at entry points 218b, 214b and exits points 220b, 216b respectively. Again, the active pixels of the object are shown as boxes with cross-hatched filling. As can be seen all those pixels touched by the edges 212b, 213b of the exemplary object are active. Thus, the minimum position of the entry or exit positions 218b, 220b of the edge 212b must be mathematically rounded down for activation, and the maximum position of the entry or exit positions 214b, 216b of the edge 213b must be mathematically rounded up for de-activation. Also, because an edge may track across several pixels in the course of traversing a scanline, the extent of any such excursion must be activated, regardless of the entry and exit points of the edge. However typical pixel sequential rendering graphic systems apply the same rasterization rule for rounding of each edge irrespective whether the object is to be activated or de-activated. Consequently this results in the pixel sequential rendering graphic systems rendering an unreliable representation of the object in the cases where the rasterization rule for rounding of edge position inherent in the page description language and graphic interface is dependent on whether the object is being activated or de-activated.